#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2020 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class Solution:
    """
    @param grid: a boolean 2D matrix
    @return: an integer
    """
    def numIslands(self, grid):
        if not grid:
            return 0

        self.num_of_islands = 0

        self.grid = grid
        self.rows = len(grid)
        self.cols = len(grid[0])

        for r in range(self.rows):
            for c in range(self.cols):
                if self.grid[r][c] != 1:
                    continue
                self.num_of_islands += 1
                self.dfs(r, c)

        return self.num_of_islands

    def dfs(self, r, c):
        if r < 0 or r >= self.rows or c < 0 or c >= self.cols:
            return

        # if (r-1 < 0 or self.grid[r-1][c] == 0) and (c-1 < 0 or self.grid[r][c-1]==0):
            #     self.num_of_islands += 1
        if self.grid[r][c] == 1:
            self.grid[r][c] = 0

            # 返回头去找, 也是需要的, 比如如下情况.
            # [ [0, 1]
            #   [1, 1] ]
            self.dfs(r-1, c)

            self.dfs(r+1, c)
            self.dfs(r, c-1)
            self.dfs(r, c+1)


def test():
    s = Solution()

    grid = [
        [1,1,0,0,0],
        [0,1,0,0,1],
        [0,0,0,1,1],
        [0,0,0,0,0],
        [0,0,0,0,1]
    ]

    ret = s.numIslands(grid)
    print(ret)


def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
